package com.atwulidun.recursion;

import java.util.ArrayList;
import java.util.List;

// 描述：给定一个n，生成n对所有可能的有效括号
public class GenerateParentheses {
    // 定义一个list来保存每种可能的情况
    List<String> list = new ArrayList<>();// 之前用的是打印出每种情况的方式，但这里需要存起来
    // 定义一个stringBuilder来追加相应的括号
    StringBuilder stringBuilder = new StringBuilder();// 之前是用一个数组来记录每次添加进来的数据
    // n为要生成的括号的对数
    int n;

    public GenerateParentheses(int n) {
        this.n = n;
    }

    // 定义回溯方法：因为不是用for循环来进行范围选择，故不用设置start和end参数；进行递归返回条件判断里面的变量就是回溯方法的其他入参，这里是left和right，类似于index
    public void backTrack(int left, int right) {
        // 递归返回的条件
        if (left == n && right == n) {
            list.add(stringBuilder.toString());// 因为是用回溯的方法，故不用对stringBuilder进行清空处理
            return;
        }
        // 先进行剪枝判断，再进行选择(这里有两种选择：即添加'('或')')
        // 若当前左括号数量大于右括号数量，则可以添加两种括号中的一种；若相等，那就只能选择添加左括号了
        // 这里用类比for循环的方式来写代码
        // 若当前left == 3,right == 2,若再做选择1，此时left == 4,right == 2,则递归直接返回
        // 若当前left == 2,right == 2,若再做选择2，此时left == 2,right == 3,则递归直接返回
        if (left > n || left < right) {
            return;
        }
            // 选择1
            stringBuilder.append("(");
            // 递归
            backTrack(left + 1, right);
            // 撤销，为了不影响下面的选择2
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);

            // 下面相当于是进入了for的另一个i
            // 选择2
            stringBuilder.append(")");
            // 递归
            backTrack(left, right + 1);
            // 撤销
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);

    }

    public static void main(String[] args) {
        GenerateParentheses generateParentheses = new GenerateParentheses(3);
        generateParentheses.backTrack(0, 0);
        System.out.println(generateParentheses.list);
    }
}
